package pers.qianyu.month_202103.date_20210328;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

/**
 * 5715. 还原排列的最少操作步数
 * https://leetcode-cn.com/problems/minimum-number-of-operations-to-reinitialize-a-permutation/
 *
 * @author mizzle rain
 * @date 2021-03-28 10:52
 */
public class ReinitializePermutation {
    public int reinitializePermutation(int n) {
        if (n <= 0) return 0;
        int[] perm = new int[n];
        for (int i = 0; i < n; i++) {
            perm[i] = i;
        }
        int[] perm2 = Arrays.copyOf(perm, perm.length);
        int cnt = 0;
        while (true) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    arr[i] = perm2[i / 2];
                }
                if (i % 2 == 1) {
                    arr[i] = perm2[n / 2 + (i - 1) / 2];
                }
            }
            perm2 = arr;
//            System.out.println(Arrays.toString(perm2));
            cnt++;
            if (Arrays.equals(perm2, perm)) {
                break;
            }
        }
        return cnt;
    }

    @Test
    public void test() {
        int r = new ReinitializePermutation().reinitializePermutation(2);
        Assert.assertEquals(1, r);
    }

    @Test
    public void test1() {
        int r = new ReinitializePermutation().reinitializePermutation(4);
        Assert.assertEquals(2, r);
    }

    @Test
    public void test2() {
        int r = new ReinitializePermutation().reinitializePermutation(6);
        Assert.assertEquals(4, r);
    }
}
